package com.my.study.structures.linkedlist;

/**
 * @author Carlos
 * @version 1.0
 * @Description 合并两个有序链表
 * @date 2021/6/9 21:54
 **/
public class MergeLinked {

    private Node head;

    /**
     * 递归合并两个有序链表
     *
     * @param firstNode
     * @param secondNode
     * @return
     */
    public static Node mergeTwoListNode(Node firstNode, Node secondNode) {
        if (firstNode == null) {
            return secondNode;
        }

        if (secondNode == null) {
            return firstNode;
        }
        // 合并后的新有序链表
        Node mergeNode;

        if (firstNode.value < secondNode.value) {
            mergeNode = firstNode;
            mergeNode.next = mergeTwoListNode(firstNode.next, secondNode);
        } else {
            mergeNode = secondNode;
            mergeNode.next = mergeTwoListNode(firstNode, secondNode.next);
        }


        return mergeNode;
    }

    /**
     * 递归合并两个有序链表
     *
     * @param firstNode
     * @param secondNode
     * @return
     */
    public static Node mergeTwoList(Node firstNode, Node secondNode) {
        if (firstNode == null) {
            return secondNode;
        }

        if (secondNode == null) {
            return firstNode;
        }

        Node head,temp;
        Node curFirst = firstNode;
        Node curSecond = secondNode;

        if (firstNode.value <= secondNode.value) {
            head = firstNode;
            curFirst = curFirst.next;
        } else {
            head = secondNode;
            curSecond = curSecond.next;
        }
        temp = head;

        while (curFirst != null && curSecond != null) {
            if (curFirst.value <= curSecond.value) {
                temp.next = curFirst;
                curFirst = curFirst.next;
            } else {
                temp.next = curSecond;
                curSecond = curSecond.next;
            }
            temp = temp.next;
        }

        if (curFirst == null) {
            temp.next = curSecond;
        }

        if (curSecond == null) {
            temp.next = curFirst;
        }

        return head;
    }

}


class Node {
    int value;
    Node next;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}
